A
弱智题,对于每一个轨道会花费 的代价,直接累加即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, c, T, ans, a[N], cnt[N];
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
memset(cnt, 0, sizeof(cnt));
cin >> n >> c;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
ans = 0;
for (int i = 1; i <= 100; i++) {
if (!cnt[i]) continue;
if (cnt[i] >= c) ans += c;
else ans += cnt[i];
}
cout << ans << endl;
}
}
B
如果没有 的限制,那就是一个求 的简单题目,直接取最大值和最小值的算术平均即可。
现在考虑加入 的贡献。我们把 变为 和 两个点,把问题转化为上面的问题。容易证明这对最后的答案没有影响。
注意 cin/cout 输出浮点数会有科学计数法的问题,需要特判奇数。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int x[N], t[N], n, T, mx, mn;
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
memset(x, 0, sizeof(x));
memset(t, 0, sizeof(t));
cin >> n;
for (int i = 1; i <= n; i++) cin >> x[i];
mx = -1e9, mn = 1e9;
for (int i = 1; i <= n; i++) {
cin >> t[i];
mx = max(mx, max(x[i] + t[i], x[i] - t[i]));
mn = min(mn, min(x[i] + t[i], x[i] - t[i]));
}
cout << (mx + mn) / 2;
if ((mx + mn) & 1) cout << ".5";
cout << endl;
}
}
C
一个1200的题楞是不会做
维护后缀最小值 ,在第 位上,最优情况可以把 至 的每一种字符全都插入进来。如果 则选择保留 ,否则执行操作拿掉这一个字符。
时间复杂度 。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], suf[N], cnt[N], n, T;
string s, ans;
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
memset(cnt, 0, sizeof(cnt));
cin >> s;
n = (int)s.size();
for (int i = 0; i < n; i++) a[i] = s[i] - '0';
suf[n] = 9;
for (int i = n - 1; i >= 0; i--) suf[i] = min(suf[i + 1], a[i]);
ans = "";
for (int i = 0; i < n; i++) {
for (int j = 0; j < suf[i]; j++)
while (cnt[j]) {
cnt[j]--;
ans += char(j + '0');
}
if (s[i] - '0' == suf[i]) ans += s[i];
else cnt[min(a[i] + 1, 9)]++;
}
for (int i = 0; i < 10; i++)
while (cnt[i]) {
cnt[i]--;
ans += char(i + '0');
}
cout << ans << endl;
}
}
D
很有意思的题目。
我们可以把两个字符串内相对的字符换到任意一个地方,并且依然保持相对关系。于是考虑把 反转,转化为把 和 的任何位置上的一个字符换到相同的位置上。
我们组出 个无序字符对 ,只有能够将这些字符对组成回文串时,才能满足要求。
时间复杂度 。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
string s1, s2;
int n, T, cnt, palin, a[N], b[N];
set<pair<int, int> > st;
map<pair<int, int>, int> mp;
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> s1 >> s2;
for (int i = 1; i <= n; i++) {
a[i] = s1[i - 1] - 'a';
b[i] = s2[i - 1] - 'a';
}
st.clear(), mp.clear();
cnt = palin = 0;
for (int i = 1; i <= n; i++) {
auto p = make_pair(a[i], b[n - i + 1]);
if (p.first > p.second) p = {p.second, p.first};
if (st.count(p)) {
mp[p]++;
cnt += (mp[p] & 1) ? 1 : -1;
if (p.first == p.second) palin += (mp[p] & 1) ? 1 : -1;
} else {
mp[p] = 1;
st.insert(p);
cnt++;
if (p.first == p.second) palin++;
}
}
if (cnt == palin && n % 2 == palin) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
E
待补。
F
待补。